package com.sise.Linked;

import java.util.HashMap;
import java.util.Map;

/**
 *      146. LRU 缓存机制
 *
 *      运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
 *      实现 LRUCache 类：
 *
 *      LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
 *      int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 *      void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。
 *      当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
 *
 *      题解：使用双向链表 + 哈希表
 *      1、为什么使用 Map ? Map<Integer, DLinkedNode> 记录 key 所对应的 节点，就不用遍历整个双向链表才可以找到节点。这里的 key 也是双向链表的 key
 *      2、双向链表：使用其特性实现 最近最少使用
 */
public class _146_LRUCache {

    // 双向链表的节点。由于题目需要自己定义数据结构，故此需要定义一个 类
    class DLinkedNode{
        int key;                // 这里的 key、value 是为了 HashMap 做准备的
        int value;
        DLinkedNode prev;       // 使用头尾部节点，完成 最近最少使用特性
        DLinkedNode next;
        public DLinkedNode(){}
        public DLinkedNode(int _key, int _value){       // 这里要用下划线，否则由于没有 this，会引用不是
            key = _key;
            value = _value;
        }
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head;       // 由于最近最少使用的原则，故此新的都要加在后面，而超出的元素在最前面，故此删掉 head，添加到 tail
    private DLinkedNode tail;

    // 类初始化
    public _146_LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null){
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    // put() 分为两部分，判断 map 中是否存在此节点，更新(添加)、将其移动到头部
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);      // 通过 map 定位是否填写过该节点
        if (node == null){
            DLinkedNode newNode = new DLinkedNode(key,value);
            cache.put(key, newNode);
            addToHead(newNode);
            ++size;

            if (size > capacity){               // 如果超过容量，那么就删除尾部节点 (tail.prev)
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);         // 切记要把 map 中的记录也删掉
                --size;
            }

        }else {
            node.value = value;                 // 如果存在则替换
            moveToHead(node);
        }

    }

    // 删除尾部节点
    private DLinkedNode removeTail() {
        DLinkedNode node = tail.prev;
        removeNode(node);
        return node;
    }

    // 将节点移动到头部节点：删除节点、添加节点到头部
    private void moveToHead(DLinkedNode node){
        removeNode(node);
        addToHead(node);
    }

    // 将节点添加到头部
    private void addToHead(DLinkedNode node) {
        node.next = head.next;          // 将头结点的下一个节点 赋值给 node ： node - > head.next
        head.next = node;               // 将头结点关联 node ： head -> node -> head.next

        node.next.prev = node;          // 这里如果写成 node = node.next.prev，那么就会报错。因为 node.next.prev 是一个值，那就是 head，以前的关联关系还没断开，所以这里要覆盖
        node.prev = head;               // head <- node
    }

    // 删除指定节点
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}
